What is an Operating Mission? An operating system is a software that manages the computer hardware. It acts as an intermediary between the user of a computer and computer hardware. The purpose of an operating system is to provide an environment in which a user can execute programs in a convenient and efficient manner. It records that the hardware must provide appropriate mechanisms to ensure the correct operation of the computer system and to prevent user programs from interfering with the proper operation of the system.

Various relevant definitions of Operating System:

• An operating system is a program that controls the execution of application programs and acts as an interface between the user of a computer and the computer hardware.


• A more common definition is that the operating system is the one program running at all times on the computer (usually called the kernel), with all else being application programs.


• An operating system is concerned with the allocation of resources and services, such as memory, processors, devices, and information. The operating system correspondingly includes programs to manage these resources, such as a traffic controller, a scheduler, memory management module, I/O programs, and a file system.

Key functions of the Operating System:

• Convenience: An OS makes a computer more convenient to use.


• Efficiency: An OS allows the computer system resources to be used in an efficient manner.


• Ability to Evolve: An OS should be constructed in such a way as to permit the effective development, testing and introduction of new system functions at the same time without interfering with service.

Types of Operating System -

• Single Tasking Operating System - This type of Operating System can run only one program at a particular time.


• Multiprogramming Operating System - A computer running more than one program at a time (like running Excel and Firefox simultaneously).


• Multitasking Operating System – Tasks sharing a common resource (like 1 CPU).


• Multiprocessing Operating System– A computer using more than one CPU at a time.


• Multithreading Operating System - This is an extension of multitasking.


• Multiuser Operating System - This refers to the system where multiple users sitting on different computers can access a single OS resource.

Primary components in a Computer System with an Operating System:

1. User


2. System and application programs


3. Operating system


4. Hardware

Every general-purpose computer consists of the hardware, operating system, system programs, and application programs. The hardware consists of memory, CPU, ALU, and I/O devices, peripheral device, and storage device. System program consists of compilers, loaders, editors, OS, etc. The application program consists of business programs, database programs. Every computer must have an operating system to run other programs. The operating system is a set of special programs that coordinate the use of the hardware among the various system programs and application programs for various users. It simply provides an environment within which other programs can do useful work. It performs basic tasks such as recognizing input from the keyboard, keeping track of files and directories on the disk, sending output to the display screen and controlling peripheral devices. OS is designed to serve two basic purposes:

1. It controls the allocation and use of the computing System’s resources among the various user and tasks.


2. It provides an interface between the computer hardware and the programmer that simplifies and makes feasible for coding, creation, debugging of application programs.

The Operating system must support the following tasks. The task is:

• Provides the facilities to create, modification of programs and data files using an editor.


• Access to the compiler for translating the user program from high-level language to machine language.


• Provide a loader program to move the compiled program code to the computer’s memory for execution.


• Provide routines that handle the details of I/O programming.

Let's look at the I/O system and few drivers related to the hardware components that the OS needs to maintain its task:
I/O System Management - The module that keeps track of the status of devices is called the I/O traffic controller. Each I/O device has a device handler that resides in a separate process associated with that device.
The I/O subsystem consists of

• A memory Management component that includes buffering caching and spooling.
• A general device driver interface.

Assembler - The input to an assembler is an assembly language program. The output is an object program plus information that enables the loader to prepare the object program for execution. At one time, the computer programmer had at his disposal a basic machine that interpreted, through hardware, certain fundamental instructions. He would program this computer by writing a series of ones and Zeros (Machine language), place them into the memory of the machine.

Compiler - The High-level languages- examples are FORTRAN, COBOL, ALGOL and PL/I are processed by compilers and interpreters. A compiler is a program that accepts a source program in a “high-level language “and produces a corresponding object program. An interpreter is a program that appears to execute a source program as if it was machine language. The same name (FORTRAN, COBOL, etc.) is often used to designate both a compiler and its associated language.

Loader - A Loader is a routine that loads an object program and prepares it for execution. There are various loading schemes: absolute, relocating and direct-linking. In general, the loader must load, relocate and link the object program. The loader is a program that places programs into memory and prepares them for execution. In a simple loading scheme, the assembler outputs the machine language translation of a program on a secondary device and a loader places it in the core. The loader places into memory the machine language version of the user’s program and transfers control to it. Since the loader program is much smaller than the assembler, those make more core available to the user’s program.

Examples of Operating System are -

• Windows (GUI based, PC)
• GNU/Linux (Personal, Workstations, ISP, File and print server, Three-tier client/Server)
• macOS (Macintosh), used for Apple's personal computers and work stations (MacBook, iMac).
• Android (Google's Operating System for smartphones/tablets/smartwatches)
• iOS (Apple's OS for iPhone, iPad and iPod Touch)

Advantages of Operating System:

1. GUI feature makes it easy to use.
2. Links the applications to the hardware, acting as an intermediary between the two.
3. Provides a user-friendly environment for the execution of programs and software.


4. Using abstraction, OS saves the details and complexity of the underlying hardware.

Introduction to process: A process is a program in execution or a process is an ‘active’ entity, as opposed to a program, which is considered to be a ‘passive’ entity.
A single program can create many processes when running multiple times; when we open a .exe or binary file multiple times, multiple instances begin (multiple processes are created).
For example,
When we write a program in C or C++ and compile it, the compiler creates binary code. The original code and binary code are both programs. When we actually run the binary code, it becomes a process.
 
What does a process look like in memory?

Text Section: A Process, sometimes known as the Text Section, also includes the current activity represented by the value of the Program Counter.
Stack: The Stack contains the temporary data such as function parameters, returns addresses, and local variables.
Data Section: Contains the global variable.
Heap Section: Dynamically allocated memory to process during its run time.
Refer to this for more details on sections.

Process States

• Single Tasking Systems(MS-DOS): In this kind of system, the second process begins only when the first process ends. By the time one process completes there might be other I/O devices, waiting for the first process to complete its task. This might lead to a delay in the process of the operating system, which is not feasible from the user's point of view. Therefore, the need arose for a multiprogramming system that can execute multiple processes at a given time. Given below is the process state diagram of the following:
  



• Multiple programming System: In this system, multiple programs share single hardware resources. However, fake parallelism is achieved by context-switching between the processes. Responsiveness between multiple programs is achieved in such a manner. The number of programs that can simultaneously run thus depends upon the size of the main memory.
  There are various states through which a processor passes to complete a particular or multiple executions. This is explained below using the process state diagram.
  Here is the basic diagram showing a 5-state model and an advanced diagram showing the 7-state model.
  
  5-State Model 7-State Model States of a process are as following:
  • New (Create) - In this step, the process is about to be created, but it is not yet created. It is the program that is present in secondary memory that will be picked up by OS to create the process.
    
    
  • Ready - New -> Ready to run. After the creation of a process, the process enters the ready state i.e. the process is loaded into the main memory. The process here is ready to run and is waiting to get the CPU time for its execution. Processes that are ready for execution by the CPU are maintained in a queue for ready processes.
    
    
  • Run - The process is chosen by the CPU for execution and the instructions within the process are executed by any one of the available CPU cores.
    
    
  • Blocked or wait - Whenever the process requests access to I/O or needs input from the user or needs access to a critical region(the lock for which is already acquired) it enters the blocked or waits for the state. The process continues to wait in the main memory and does not require a CPU. Once the I/O operation is completed the process goes to the ready state.
    
    
  • Terminated or completed - Process is killed as well as PCB is deleted.
    
    
  • Suspend ready - Process that was initially in the ready state but were swapped out of main memory(refer Virtual Memory topic) and placed onto external storage by scheduler are said to be in suspending ready state. The process will transition back to the ready state whenever the process is again brought onto the main memory. Linux uses swap space and partition to do this task.
    
    
  • Suspend wait or suspend blocked - Similar to suspend ready but uses the process which was performing I/O operation and lack of main memory caused them to move to secondary memory.
    When work is finished it may go to suspend ready.
    

Process Control Block or PCB Various Attributes or Characteristics of a Process are:

1. Process Id: A unique identifier assigned by the operating system

2. Process State: Can be ready, running, etc.

3. CPU registers: Like the Program Counter (CPU registers must be saved and 

                         restored when a process is swapped in and out of CPU)

4. Accounts information: This includes the amount of CPU used for the process 

                         execution, time limits, execution ID etc.

5. I/O status information: For example, devices allocated to the process, 

                         open files, etc.

6. CPU scheduling information: For example, Priority (Different processes 

                         may have different priorities, for example, a short process maybe 

                         assigned a low priority in the shortest job first scheduling)

All of the above attributes of a process are also known as the context of the process.
Every process has its own program control block(PCB), i.e each process will have a unique PCB. All of the above attributes are part of the PCB.
A process control block (PCB) contains information about the process, i.e. registers, quantum, priority, etc. The process table is an array of PCBs, which means logically contains a PCB for all of the current processes in the system.

• Pointer - It is a stack pointer that is required to be saved when the process is switched from one state to another to retain the current position of the process.
• Process state - It stores the respective state of the process.
• Process number - Every process is assigned with a unique id known as process ID or PID which stores the process identifier.
• Program counter - It stores the counter which contains the address of the next instruction that is to be executed for the process.
• Register - These are the CPU registers which include: accumulator, base, registers, and general-purpose registers.
• Memory limits - This field contains information about the memory management system used by the operating system. This may include the page tables, segment tables etc.
• Open files list - This information includes the list of files opened for a process.

Context Switching The process of saving the context of one process and loading the context of another process is known as Context Switching. In simple terms, it is like loading and unloading the process from the running state to the ready state.

When does context switching happen? 1. When a high-priority process comes to a ready state (i.e. with higher priority than the running process).
2. An Interrupt occurs.
3. User and kernel-mode switch (It is not necessary though).
4. Preemptive CPU scheduling is used.

Context Switch vs Mode Switch A mode switch occurs when the CPU privilege level is changed, for example when a system call is made or a fault occurs. The kernel works in more a privileged mode than a standard user task. If a user process wants to access things that are only accessible to the kernel, a mode switch must occur. The currently executing process need not be changed during a mode switch.
A mode switch typically occurs for a process context switch to occur. Only the kernel can cause a context switch.

CPU and IO Bound Processes If the process is intensive in terms of CPU operations then it is called the CPU-bound process. Similarly, If the process is intensive in terms of I/O operations then it is called an IO-bound process.
There are three types of process schedulers.

1. Long Term or job scheduler: It brings the new process to the 'Ready State'. It controls the Degree of Multi-programming, i.e., the number of processes present in the ready state at any point in time. It is important that the long-term scheduler makes a careful selection of both IO and CPU-bound processes.
   
   
2. Short term or CPU scheduler: It is responsible for selecting one process from the ready state for scheduling it on the running state.
   Note: Short-term scheduler only selects the process to schedule it doesn't load the process on running. The
   Dispatcher is responsible for loading the process selected by the Short-term scheduler on the CPU (Ready to Running State) Context switching is done by dispatcher only. A dispatcher does the following:
   
   1. Switching context.
      
   2. Switching to user mode.
      
   3. Jumping to the proper location in the newly loaded program.
   
   
   
3. Medium-term scheduler It is responsible for suspending and resuming the process. It mainly does swapping (moving processes from main memory to disk and vice versa). Swapping may be necessary to improve the process mix or because a change in memory requirements has overcommitted available memory, requiring memory to be freed up.

Multiprogramming - We have many processes ready to run. There are two types of multiprogramming:

1. Pre-emption - Process is forcefully removed from CPU. Pre-emption is also called as time sharing or multitasking.
   
   
2. Non pre-emption - Processes are not removed until they complete the execution.
   

Degree of multiprogramming -
The number of processes that can reside in the ready state at maximum decides the degree of multiprogramming, e.g., if the degree of programming = 100 means 100 processes can reside in the ready state at maximum.

There are different queues of processes (in an operating system):

• Ready Queue: The set of all processes that are in main memory and are waiting for CPU time is kept in the ready queue.


• Job Queue: Each new process goes into the job queue. Processes in the job queue reside on mass storage and await the allocation of main memory.


• Waiting (Device) Queues: The set of processes waiting for allocation of certain I/O devices is kept in the waiting (device) queue. The short-term scheduler (also known as CPU scheduling) selects a process from the ready queue and yields control of the CPU to the process

Short-Term Scheduler and Dispatcher - Consider a situation, where various processes residing in the ready queue and waiting for execution. But CPU can't execute all the processes of ready queue simultaneously, the operating system has to choose a particular process on the basis of scheduling algorithm used. So, this procedure of selecting a process among various processes is done by scheduler. Now here the task of scheduler completed. Now dispatcher comes into the picture as scheduler has decided a process for execution, it is dispatcher who takes that process from ready queue to the running status, or you can say that providing CPU to that process is the task of the dispatcher.

Example - There are 4 processes in ready queue, i.e., P1, P2, P3, P4; They all have arrived at t0, t1, t2, t3 respectively. First in First out scheduling algorithm is used. So, scheduler decided that first of all P1 has come, so this is to be executed first. Now dispatcher takes P1 to the running state.




Difference between the Scheduler and Dispatcher:

Properties	DISPATCHER	SCHEDULER
Definition:	Dispatcher is a module that gives control of CPU to the process selected by short term scheduler	Scheduler is something which selects a process among various processes
Types:	There are no diifrent types in dispatcher.It is just a code segment.	There are 3 types of scheduler i.e. Long-term, Short-term, Medium-term
Dependency:	Working of dispatcher is dependednt on scheduler.Means dispatcher have to wait untill scheduler selects a process.	Scheduler works idependently.It works immediately when needed
Algorithm:	Dispatcher has no specific algorithm for its implementation	Scheduler works on various algorithm such as FCFS, SJF, RR etc.
Time Taken:	The time taken by dispatcher is called dispatch latency.	TIme taken by scheduler is usually negligible.Hence we neglect it.
Functions:	Dispatcher is also responsible for:Context Switching, Switch to user mode, Jumping to proper location when process again restarted	The only work of scheduler is selection of processes.

Below are different time with respect to a process.

1. Arrival Time: Time at which the process arrives in the ready queue.


2. Completion Time: Time at which process completes its execution.


3. Burst Time: Time required by a process for CPU execution.


4. Turn Around Time: Time Difference between completion time and arrival time.
   

   Turn Around Time = Completion Time - Arrival Time

5. Waiting Time(W.T): Time Difference between turn around time and burst time.
   

   Waiting Time = Turn Around Time - Burst Time

6. Response Time: Time difference between arrival time and the first time the process gets CPU.

Example: Suppose we are given to calculate each type of time for the process P0 for the Gantt chart:

In the diagram from time 0 to 1, the CPU is free. Time slot 1 to 3 has been scheduled for P0, 3 to 5 has been scheduled for P1 and 5 to 6 are again scheduled to P0.
So for P0:

• Arrival Time (time of arrival into PC) = 1


• Completion Time (time of completion at PC) = 6


• Burst Time (Time taken by P0) = From 1 to 3 P0 takes 2 units of time and from 5 to 6 P0 takes 1 unit of time. So, in all Burst Time for P0 is 3.


• Turn Around Time = Completion Time - Arrival Time = 6 - 1 = 5.


• Waiting Time = Turn Around Time - Burst Time = 5 - 3 = 2.


• Response Time = 0 since the process got the CPU immediately.

Goals of a Scheduling Algorithm:

1. Maximum CPU Utilization: CPU must not be left idle and should be used to the full potential


2. Maximum Throughput: Throughput refers to the number of jobs completed per unit time. So the CPU must try to execute maximum number of jobs per unit time.


3. Minimum Turnaround time: Time between arrival and completion must be minimum.


4. Minimum Waiting Time: Total amount of time in the ready queue must be minimum.


5. Minimum Response Time: Difference between the arrival time and the time at which the process gets the CPU must be mininmum.


6. Fair CPU Allocation: No job must be starved.

Different Scheduling Algorithms

• First Come First Serve (FCFS) - Simplest scheduling algorithm that schedules according to arrival times of processes. First come first serve scheduling algorithm process that requests the CPU first is allocated the CPU first. It is implemented by using the FIFO queue. FCFS is a non-preemptive scheduling algorithm.
  


• Shortest Job First (SJF) - Process which have the shortest burst time are scheduled first.If two processes have the same bust time then FCFS is used to break the tie. It is a non-preemptive scheduling algorithm.


• Longest Job First (LJF) - It is similar to SJF scheduling algorithm. But, in this scheduling algorithm, we give priority to the process having the longest burst time. This is non-preemptive in nature i.e., when any process starts executing, can't be interrupted before complete execution.


• Shortest Remaining Time First (SRTF) - It is preemptive mode of SJF algorithm in which jobs are schedule according to shortest remaining time.


• Longest Remaining Time First (LRTF) - It is preemptive mode of LJF algorithm in which we give priority to the process having largest burst time remaining.


• Round Robin Scheduling (RR) - Each process is assigned a fixed time(Time Quantum/Time Slice) in cyclic way. It is designed especially for the time-sharing system. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1-time quantum.


• Priority Based scheduling (Non-Preemptive) - In this scheduling, processes are scheduled according to their priorities, i.e., highest priority process is scheduled first. If priorities of two processes match, then schedule according to arrival time. Here starvation of process is possible.


• Highest Response Ratio Next (HRRN) - In this scheduling, processes with highest response ratio is scheduled. This algorithm avoids starvation.
  

  Response Ratio = (Waiting Time + Burst time) / Burst time

• Multilevel Queue Scheduling - According to the priority of process, processes are placed in the different queues. Generally high priority process are placed in the top level queue. Only after completion of processes from top level queue, lower level queued processes are scheduled. It can suuffer from starvation.


• Multi level Feedback Queue Scheduling - It allows the process to move in between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-priority queue.

Some useful facts about Scheduling Algorithms:

1. FCFS can cause long waiting times, especially when the first job takes too much CPU time.
   
   
2. Both SJF and Shortest Remaining time first algorithms may cause starvation. Consider a situation when the long process is there in the ready queue and shorter processes keep coming.
   
   
3. If time quantum for Round Robin scheduling is very large, then it behaves same as FCFS scheduling.
   
   
4. SJF is optimal in terms of average waiting time for a given set of processes,i.e., average waiting time is minimum with this scheduling, but problems are, how to know/predict the time of next job.

FCFS (First-come-First-serve) follows the principle of FIFO (First-in-First-out). It is the simplest scheduling algorithm. FCFS simply queues processes in the order that they arrive in the ready queue. In this, the process which comes first will be executed first and the next process starts only after the previous gets fully executed. It is a non-preemptive algorithm. Let's look at this problem:

Only the processes in the ready queue are to be considered. Since there is no preemption, once the job starts it is going to run until its completion. Now let's look at the Gantt chart:

Now, let's compute each type of time using concepts and formulae, that we studied in the previous lecture. Now the chart looks like this:


So, Average waiting time = (0+1+6+9+17)/5 = 33/5
and Average turn-around time = (2+7+10+18+29)/5 = 74/5

Example:

Implementation:

1-  Input the processes along with their burst time (bt).
2-  Find the waiting time (wt) for all processes.
3-  As the first process that comes need not to wait so 
    waiting time for process 1 will be 0 i.e. wt[0] = 0.
4-  Find waiting time for all other processes i.e. for
     process i -> 
       wt[i] = bt[i-1] + wt[i-1] .
5-  Find turnaround time = waiting_time + burst_time 
    for all processes.
6-  Find average waiting time = 
                 total_waiting_time / no_of_processes.
7-  Similarly, find average turnaround time = 
                 total_turn_around_time / no_of_processes.

Important Points:

1. Simple and Easy to implement
2. Non-preemptive
3. Average Waiting Time is not optimal
4. Can not utilize resources in parallel: Results in Convoy effect. Convoy Effect is a phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to a few slow processes. Consider a situation when many IO-bound processes are there and one CPU bound process. The IO bound processes have to wait for CPU bound process when the CPU bound process acquires CPU. The IO-bound process could have taken CPU for some time, then used IO devices. The diagram below is a good analogy to the problem:
   

The Shortest-Job-First (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next. It is a non-preemptive algorithm. Being a non-preemptive algorithm, the first process assigned to the CPU is executed till completion, then the process whose burst time is minimum is assigned next to the CPU and hence it continues.

Algorithm:

1- Sort all the processes in increasing order 
   according to burst time.
2- Then simply, apply FCFS.

Let's look at the following non preemptive SJFS problem and understand the stepwise execution:

Now lets draw the Gantt chart to the following problem:


How to compute below times in SJF using a program?

1. Completion Time: Time at which process completes its execution.
2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time - Arrival Time


3. Waiting Time(W.T): Time Difference between turn around time and burst time.
   Waiting Time = Turn Around Time - Burst Time

Therefore the final chart showing all type of times are as follows:


So, Average turn-around time = (5+11+6+17)/4 = 39/4
and Average waiting time = (0+7+3+9)/4 = 19/4

Example:

Some of the key points are as follows:

• Shortest Job first has the advantage of having a minimum average waiting time among all scheduling algorithms.
  
• It is a Greedy Algorithm.
  
• It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of ageing.
  
• It is practically infeasible as Operating System may not know burst time and therefore may not sort them. While it is not possible to predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times. SJF can be used in specialized environments where accurate estimates of running time are available.
  

In the previous post, we have discussed SJF which is a non-preemptive scheduling algorithm. In this post, we will discuss the preemptive version of SJF known as Shortest Remaining Time First (SRTF).

In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time.

Implementation:

1- Traverse until all process gets completely executed.
   a) Find process with minimum remaining time at every single time lap.
   b) Reduce its time by 1.
   c) Check if its remaining time becomes 0.
   d) Increment the counter of process completion.
   e) Completion time of current process = current_time +1;
   f) Calculate the waiting time for each completed process.
         wt[i]= Completion time - arrival_time-burst_time
   g) Increment time lap by one.
      
2- Find turnaround time (waiting_time+burst_time).

   Let's look at the below problem.

At first, the P0 is scheduled and it runs for 1 unit of time. P1 also around at 1 unit. So, now the remaining time of P0(i.e., 7) is compared to the burst time of P1(i.e., 4). The lesser is scheduled, here P1 is scheduled. Again it runs for 1 unit when P2 arrives. The same comparison is done. Since P1 has 3 remaining unit time which is less than P2, it is continued to be scheduled. At 3 P3 also arrives whose burst time is 5. Being more than the remaining time of P2 that is 2, P2 is continued to be scheduled until completion. Then P3 is scheduled whose burst time is 5. This runs till completion followed by P2.
All the breakdowns can be seen in the below and the Gantt chart:


Gantt chart for the process:


Now let's calculate all other time using the basic formulae.


So, Average turn around time = (17+4+24+7)/4 = 52/4
and Average waiting time = (9+0+15+2)/4 = 26/4

Example:

Process	Duration	Order	Arrival Time
P1	9	1	0
P2	2	2	2

P1 waiting time: 4-2 = 2
P2 waiting time: 0
The average waiting time(AWT): (0 + 2) / 2 = 1

Advantage:

1. Short processes are handled very quickly.
2. The system also requires very little overhead since it only makes a decision when a process completes or a new process is added.
3. When a new process is added the algorithm only needs to compare the currently executing process with the new process, ignoring all other processes currently waiting to execute.

Disadvantage:

1. Like shortest job first, it has the potential for process starvation.
2. Long processes may be held off indefinitely if short processes are continually added.
3. It is impractical since it is not possible to know the burst time of every process in ready queue in advance.

LRTF (Longest-Remaining-Time-First) is the pre-emptive version of the LJF algorithm. In this scheduling algorithm, we find the process with the maximum remaining time and then process it. We check for the maximum remaining time after some interval of time (say 1 unit each) to check if another process having more Burst Time arrived up to that time.
The algorithm stands as:

1) Sort the processes in increasing order of their arrival time.
2) Choose the process having the least arrival-time but the most burst-time. 
   Execute it for 1 unit/quantum. 
   Check if any other process arrives upto that point of execution.
3) Repeat above steps until all processes have been executed.

As an example, consider the following 4 processes (P1, P2, P3, P4):

Process   Arrival time   Burst Time

P1            1 ms          2 ms

P2            2 ms          4 ms

P3            3 ms          6 ms

P4            4 ms          8 ms  

Execution:

1. At t = 1, Available Process : P1. So, select P1 and execute 1 ms.
   
2. At t = 2, Available Process : P1, P2. So, select P2 and execute 1 ms (since BT(P1)=1 which is less than BT(P2) = 4)
   
3. At t = 3, Available Process : P1, P2, P3. So, select P3 and execute 1 ms (since, BT(P1) = 1 , BT(P2) = 3 , BT(P3) = 6).
   
4. Repeat the above steps until the execution of all processes.
   

Note that CPU will be idle for 0 to 1 unit time since there is no process available in the given interval.

Gantt chart will be as following below,




Output:

Total Turn Around Time = 68 ms

So, Average Turn Around Time = 68/4 = 17.00 ms



And, Total Waiting Time = 48 ms

So Average Waiting Time = 48/4 = 12.00 ms 

Non-Preemptive Priority scheduling: It is a non-preemptive algorithm and one of the most common scheduling algorithms in batch systems. Each process is assigned a priority. The process with the highest priority is to be executed first and so on.
Processes with the same priority are executed on the FCFS scheme. Priority can be decided based on memory requirements, time requirements or any other resource requirement.
Algorithm:

1- First input the processes with their burst time 
   and priority.
2- Sort the processes, burst time and priority
   according to the priority.
3- Now simply apply FCFS algorithm.

Let's look at the following problem with P2 set as the highest priority.


At first, P0 enters into scheduling since it arrives first. After its completion, the other 3 processes arrive. Now, priority comes into the picture. The process with the highest priority is scheduled. Here it is P2, followed by P3 and P1.

Now let's look at the Gantt chart:


The final chart looks like this:


Example:


Pre-emptive Priority Scheduling: This follows preemption where one process can be pre-empted and replaced by another process. Let's look at a similar problem as taken above and understand the working of this algorithm:


At first, P0 is scheduled and it runs for 1 unit followed by the arrival of P1. Since P1 has less priority than P0, P0 continues for 1 more unit, Now P2 arrives which has a greater priority and hence is scheduled. It runs until completion and then P3 follows which has a greater priority among the present processes. It completes and then the priority of the remaining processes are compared i.e., P0 and P1. P0 having greater priority finishes its remaining 1 unit of time and then P1 follows.

Below is the Gantt chart of the following process:


Here is the final chart showing all the time:


Note: A major problem with priority scheduling is indefinite blocking or Starvation. A solution to the problem of indefinite blockage of the low-priority process is ageing. Aging is a technique of gradually increasing the priority of processes that wait in the system for a long period of time.

Round-Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot (also called quantum). Once that chunk of time is completed, the process is context-switched with the next in the queue. It is the most common and practically usable scheduling algorithm, as it doesn't require the system to estimate the burst-time of a process. Calculation of burst-time is practically not possible as no one can predict how long a process will take to execute. It although has a minor disadvantage of the overhead of context-switching (some time gets wasted in the process). Let's try to understand the working using the following problem, with given Time Quantum of 2 units:


Each process runs for 2 unit of time, followed by the next process. The whole process runs in a circular manner.


Here is the Gantt chart of the above problem:


Here is the final chart showing all type of times:



The algorithm to calculate the various time statistics are as follows:

1) Create an array rem_bt[] to keep track of remaining
   burst time of processes. This array is initially a 
   copy of bt[] (burst times array)
2) Create another array wt[] to store waiting times
   of processes. Initialize this array as 0.
3) Initialize time : t = 0
4) Keep traversing all processes while all processes
   are not done. Do following for the ith process if it is not done yet.
    a- If rem_bt[i] > quantum
       (i)  t = t + quantum
       (ii) bt_rem[i] -= quantum;
    c- Else // Last cycle for this process
       (i)  t = t + bt_rem[i];
       (ii) wt[i] = t - bt[i]
       (ii) bt_rem[i] = 0; // This process is over

Once we have waiting times, we can compute turn around time tat[i] of a process as sum of waiting and burst times, i.e., wt[i] + bt[i]

Multi-level Queue Scheduling is required when we group processes into some specific categories. e.g. Foreground (interactive) and Background (batch) processes. These two classes have different scheduling needs. System processes are of the highest priority (extremely critical), then comes Interactive processes followed by Batch and Student processes.

Ready Queue is divided into separate queues for each class of processes. For example, let us take three different types of process System processes, Interactive processes, and Batch Processes. All three process has its own queue. Now, look at the below figure.



All three different types of processes have their own queue. Each queue has its own Scheduling algorithm. For example, queue 1 and queue 2 uses Round Robin while queue 3 can use FCFS to schedule there processes.

Scheduling among the queues : What will happen if all the queues have some processes? Which process should get the CPU? To determine this Scheduling among the queues is necessary. There are two ways to do so -

1. Fixed priority preemptive scheduling method - Each queue has absolute priority over lower priority queue. Let us consider following priority order queue 1 > queue 2 > queue 3.According to this algorithm no process in the batch queue(queue 3) can run unless queue 1 and 2 are empty. If any batch process (queue 3) is running and any system (queue 1) or Interactive process(queue 2) entered the ready queue the batch process is preempted.


2. Time slicing - In this method each queue gets certain portion of CPU time and can use it to schedule its own processes.For instance, queue 1 takes 50 percent of CPU time queue 2 takes 30 percent and queue 3 gets 20 percent of CPU time.

Example Consider the below table of four processes under Multilevel queue scheduling. Queue number denotes the queue of the process.



Priority of queue 1 is greater than queue 2. queue 1 uses Round Robin (Time Quantum = 2) and queue 2 uses FCFS.

Below is the gantt chart of the problem :


At starting both queues have process so process in queue 1 (P1, P2) runs first (because of higher priority) in the round robin fashion and completes after 7 units then process in queue 2 (P3) starts running (as there is no process in queue 1) but while it is running P4 comes in queue 1 and interrupts P3 and start running for 5 second and after its completion P3 takes the CPU and completes its execution.

MLFQ (Multilevel-Feedback-Queue) scheduling is a modification to the MLQ (Multilevel-Queue) which allows processes to move between queues. It keeps analyzing the behavior (time of execution) of processes, according to which it changes its priority.

Now let us suppose that queues 1 and 2 follow round robin with time quantum 4 and 8 respectively and queue 3 follow FCFS. One implementation of MFQS can be:

1. When a process starts executing then it first enters queue 1.


2. In queue 1 process executes for 4 unit and if it completes in this 4 unit or it gives CPU for I/O operation in this 4 unit than the priority of this process does not change and if it again comes in the ready queue than it again starts its execution in Queue 1.
3. If a process in queue 1 does not complete in 4 unit then its priority gets reduced and it shifted to queue 2.
4. Above points 2 and 3 are also true for queue 2 processes but the time quantum is 8 unit. In a general case if a process does not complete in a time quantum than it is shifted to the lower priority queue.
5. In the last queue, processes are scheduled in FCFS manner.
6. A process in lower priority queue can only execute only when higher priority queues are empty.
7. A process running in the lower priority queue is interrupted by a process arriving in the higher priority queue.

NOTE: A process in the lower priority queue can suffer from starvation due to some short processes taking all the CPU time. A simple solution can be to boost the priority of all the process after regular intervals and place them all in the highest priority queue.

What is the need for such a complex scheduling algorithm?

• Firstly, it is more flexible than the multilevel queue scheduling.
• To optimize turnaround time algorithms like SJF is needed which require the running time of processes to schedule them. But the running time of the process is not known in advance. MFQS runs a process for a time quantum and then it can change its priority(if it is a long process). Thus it learns from past behavior of the process and then predicts its future behavior. This way it tries to run a shorter process first thus optimizing turnaround time.
• MFQS also reduces the response time.

On the basis of synchronization, processes are categorized as one of the following two types:

1. Independent Process: Execution of one process does not affect the execution of other processes.


2. Cooperative Process: Execution of one process affects the execution of other processes.

So far we have discussed Independent processes where each process had there own address space, and they did not require to communicate with other processes. But the problem arises in the case of Cooperative process because resources are shared in Cooperative processes and various processes communicate with each other.
In this respect, we here will be discussing the problems in process synchronization, in the case of single PC inter-process communication, due to concurrent execution.

Let's look at the below example

List of Global Variable:
The Producer:
The Consumer:
Here we have written codes for Producer and Consumer. We have a few global variables which are shared among both the Producer and Consumer The Producer keeps on adding elements to by increasing the count by 1, each time it adds an element. The consumer, on the other hand, decreases the value of count by 1 each time an item is taken out. This process goes on and is enitled to be preempted at any point of time when the Consumer and producer are needed to be switched between.

Let's delete the unnecessary part of the code and focus on the locus of understanding, count++ and count--. These are not any simple instructions but are converted to the following internal assembly instructions.

count in Producer:
count in Consumer:
Let's analyze it: Let the value of count be 8 in the Producer part. If in the producer part, just after the register is incremented and before the count gets updated, the process is preempted to some other process, the problem arises. Now if the control flows to Consumer, the reg of the consumer will get value 8 instead of 9. On completion the count = 7 in Consumer part. When the control flows back to the Producer, the process resumes from where it had stopped and count in Producer gets 9. Therefore we have inconsistent values for Producer and Consumer.
This inconsistency among the interdependent stream of execution where each step is related to one another leads to the Race Condition.

Race Condition: Several processes access and process the manipulations over the same data concurrently, then the outcome depends on the particular order in which the access takes place.

Let's look at another example:
If there is no preemption in this program, then the execution goes smoothly and y becomes 7. But suppose just after the if condition in fun1(), preemption occurs, then the control flows to fun2(), where x is incremented to 3. When the flows go back to fun1() the if condition will never satisfy and we won't get the desired value of y as 7. This happens because of the Race Condition.


Critical Section: Critical section is a code segment that can be accessed by only one process at a time. The critical section contains shared variables which need to be synchronized to maintain consistency of data variables.
Let's look at the following example:

Due to preemption, we get the value of balance as 100 in Deposit() and as 90 in Withdraw(). This inconsistency is called the Race Condition and it occurs due to the preemption along the critical section of the problem. Therefore, we need a mechanism to deal with such cases. The mechanism includes putting up conditions in the entry or exit section.

Entry Section: It is part of the process which decides the entry of a particular process in the Critical Section, out of many other processes.
Exit Section: This process allows the other process that is waiting in the Entry Section, to enter into the Critical Sections. It checks that a process that after a process has finished execution in Critical Section can be removed through this Exit Section.
Remainder Section: The other parts of the Code other than Entry Section, Critical Section and Exit Section is known as Remainder Section.


Any solution to the critical section problem must satisfy these four requirements or we can say that there are four goals of synchronization algorithm:

1. Mutual Exclusion: If a process is executing in its critical section, then no other process is allowed to execute in the critical section.


2. Progress: If no process is executing in the critical section and other processes are waiting outside the critical section, then only those processes that are not executing in their remainder section can participate in deciding which will enter in the critical section next, and the selection can not be postponed indefinitely.


3. Bounded Waiting(Fair): Abound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.


4. Performance: The mechanism that allows only one process to enter the critical section should be fast. This mechanism is referred to as the locking mechanism and can be implemented in two ways, hardware or software mechanism. The hardware-based mechanism is generally faster since it only involves the registers.

Note: Mutual Exclusion and Progress are mandatory goals for synchronization mechanism.

Overview of Synchronization Mechanism:

1. Disabling Interrupts: In this, a process tells the processor that it is undergoing a critical section job and it must not be interrupted before its completion. Now, this might sound good but it comes with various serious problems. This sort of mechanism works only with a single processor system and not in multiprocessor systems. The second and more serious problem is that allowing user processes to stop interruption might lead to system failure or security issues. Therefore, this is not feasible.


2. Locks or Mutex: A mutex is a binary variable whose purpose is to provide a locking mechanism. It is used to provide mutual exclusion to a section of code, which means only one process can work on a particular code section at a time. This can be implemented in both software and hardware. It is the building block of all other mechanisms.



3. Semaphores: A semaphore is simply a variable. This variable is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment. The two most common kinds of semaphores are counting semaphores and binary semaphores. Counting semaphore can take non-negative integer values and Binary semaphore can take the value 0 & 1. only.



4. Monitors: Monitor is one of the ways to achieve Process synchronization. The monitor is supported by programming languages to achieve mutual exclusion between processes. For example Java Synchronized methods. Java provides wait() and notify() constructs.

Few applications of Synchronization are:

• Producer-Consumer Problem


• Dining Philosopher Problem


• Bounded Buffer Problem


• Reader-Writer Problem

In the database, operations frequently need to carry out atomic transactions, in which the entire transaction must either complete or not occur at all. The classic example is a transfer of funds, which involves withdrawing funds from one account and depositing them into another - Either both halves of the transaction must complete, or neither must complete.
Operating Systems can be viewed as a database in terms of needs and problems, in that, an OS can be said to manage a small database of process-related information. As such, OSes can benefit from emulating some of the techniques originally developed for databases. Here we first look at some of those techniques, and then how they can be used to benefit OS development.

System Model:

• A transaction is a series of actions that must either complete in its entirety or must be rolled-back as if it had never commenced.
  
• The system is considered to have three types of storage:
  
  • When system crashed volatile storage usually gets lost.
    
  • When a system crashed non-volatile storage usually survives system crashes, but may still get lost.
    
  • Stable storage "never" gets lost or damaged. In practice, this is implemented using multiple copies stored on different media with different failure modes.

Log-Based Recovery:

• Before each step of a transaction is conducted, an entry is written to a log on stable storage:
  
  • Each transaction has a unique serial number.
    
  • The first entry is a "start"
    
  • Transaction number is mentioned for every data changing entry specifically(the old value, and the new value).
    
  • The final entry is a "commit".
    
  • All transactions are idempotent - The can be repeated any number of times and the effect is the same as doing them once. Likewise, they can be undone any number of times and the effect is the same as undoing them once. ( I.e. "change x from 3 to 4", rather than "add 0 to x" ).
• Any transaction which has "commit" recorded in the log can be redone from the log information, after a crash. Any transaction can be undone if it has "start" but not "commit".

Checkpoints:

• When system got crashed, all data can be recovered using the system described above, by going through the entire log and performing either redo or undo operations on all the transactions listed there.
  
• Unfortunately this approach can be slow and wasteful because many transactions are repeated that were not lost in the crash.
  
• Alternatively, one can periodically establish a checkpoint, as follows:
  
  • Use stable storage to Write all data that has been affected by recent transactions (since the last checkpoint).
    
  • Write a entry to the log.
• One only needs to find transactions that did not commit to recovering crash prior to the most recent checkpoint. Specifically one looks back from the end of the log for the last record and then looks backward from there for the most recent transaction that started before the checkpoint. Only that transaction and the ones more recent need to be redone or undone.

Concurrent Atomic Transactions:

• As discussed above log-based recovery assumed that only one transaction could be conducted at a time. For now, we can relax that restriction, and allow multiple transactions to occur concurrently, while still keeping each individual transaction atomic.
  
  Serializability:
  
  • Figure 1 below shows a schedule in which transaction 0 reads and writes data items A and B, followed by transaction 1 which also reads and writes A and B. The two transactions are conducted serially this is termed a serial schedule. There are N! possible serial schedules for any N transactions.
    
  • A nonserial schedule is one in which the steps of the transactions are not completely serial, i.e. they interleave in some manner. These schedules are not necessarily bad or wrong, so long as they can be shown to be equivalent to some serial schedule. A nonserial schedule that can be converted to a serial one is said to be conflict serializable, such as that shown in Figure 2 below. Legal steps in the conversion are as follows:
    
    • Two operations from different transactions are said to be conflicting if they involve the same data item and at least one of the operations is a write operation. If operations from two transactions are either involve different data items or do not involve any write operations then these transactions are non-conflicting.
      
    • If two operations in a schedule are from two different transactions and if they are non-conflicting, can be swapped.
      
    • A schedule is conflict serializable if there exists a series of valid swap that converts the schedule into a serial schedule.
  
  
  
  
  
  
  
  
  Locking Protocol:
  
  • Serializability can be assured by using locks on data items during atomic transactions.
    
  • Exclusive and shared locks correspond to the Readers and Writers problem discussed above.
    
    • The two-phase locking protocol operates in two phases:
      
    • During the growing phase, the transaction continues to gain additional locks on data items as it needs them, and has not yet relinquished any of its locks.
      
    • In the shrinking phase, it relinquishes locks. After releasing any lock a transaction then is in the shrinking phase and cannot acquire any more locks.
  • The two-phase locking protocol can be proven to yield serializable schedules, but it does not guarantee avoidance of deadlock. There may also be perfectly valid serializable schedules that are unobtainable with this protocol.
  
  Timestamp-Based Protocols:
  
  • Each transaction is issued a unique timestamp entry before it begins execution under the timestamp protocol. The system clock is accessed by all processes on the system for the system time or some non-decreasing serial number. TS(T_i) is the timestamp for transaction.
    
  • All generated schedules are equivalent to a serial schedule generated in timestamp order.
    
  • There are two timestamps the W-timestamp and the R-timestamp associated with each data. The timestamp of the last transaction to successfully write the data item is the W-timestamp, and the stamp of the last transaction to successfully read from it the R-timestamp. (Note: These are the respective transaction's timestamps of the, not the time at which the read or write occurred.)
  The timestamps are used in the following manner:
  
  Suppose transaction Tⁱ issues a read on data item Q:
  • If TS( T_i ) < the W-timestamp for Q, then it is attempting to read data that has been changed. T_i is rolled back and restarted with a new timestamp.
    
  • If TS( T_i ) > the W-timestamp for Q, then the R-timestamp for Q is updated to the later of its current value and TS( T_i ).
  Suppose T_i issues a write on Q:
  • If TS( T_i ) < the R-timestamp for Q, then it is attempting to change data that has already been read in its unaltered state. T_i is rolled back and restarted with a new timestamp.
    
  • If TS( T_i ) < the W-timestamp for Q it is also rolled back and restarted, for similar reasons.
    Else, the operation proceeds and the W-timestamp for Q is updated to TS( T_i ).

A process can be of two types:

• Independent process.
• Co-operating process.

An independent process is not affected by the execution of other processes while a co-operating process can be affected by other executing processes.
Though one can think that those processes, which are running independently, will execute very efficiently but in practice, there are many situations when co-operative nature can be utilized for increasing computational speed, convenience, and modularity.
Interprocess communication (IPC) is a set of interfaces, which is usually programmed in order for the programs to communicate between a series of processes. This allows running f program concurrently in an Operating System. These are methods in IPC:

1. Pipes (Same Process) - This allows the flow of data in one direction only. Analogous to simplex systems (Keyboard). Data from the output is usually buffered until the input process receives it which must have a common origin.
   


2. Names Pipes (Different Processes) - This is a pipe with a specific name it can be used in processes that don't have a shared common process origin. E.g. in FIFO, where the data is written to a pipe, is first named.
   


3. Message Queuing - This allows messages to be passed between processes using either a single queue or several message queue. This is managed by system kernel these messages are coordinated using an API.
   
   
4. Semaphores - This is used in solving problems associated with synchronization and to avoid race condition. These are integer values which are greater than or equal to 0.
   
   
5. Shared memory - This allows the interchange of data through a defined area of memory. Semaphore values have to be obtained before data can get access to shared memory.
   
   
6. Sockets - This method is mostly used to communicate over a network between a client and a server. It allows for a standard connection which is computer and OS independent.
   

Inter-Process Communication through shared memory is a concept where two or more processes can access the common memory. And communication is done via this shared memory where changes made by one process can be viewed by another process.
The problem with pipes, FIFO and message queue – is that for two processes to exchange information. The information has to go through the kernel.

• Server reads from the input file.
• The server writes this data in a message using either a pipe, FIFO or message queue.


• The client reads the data from the IPC channel, again requiring the data to be copied from kernel’s IPC buffer to the client’s buffer.


• Finally the data is copied from the client’s buffer.



A total of four copies of data are required (2 reads and 2 writes). So, shared memory provides a way by letting two or more processes share a memory segment. With Shared Memory the data is only copied twice – from input file into shared memory and from shared memory to the output file.

SYSTEM CALLS USED ARE:

ftok(): is use to generate a unique key.

shmget():  int shmget(key_t,size_tsize,intshmflg); upon successful completion,
shmget() returns an identifier for the shared memory segment.

shmat(): Before you can use a shared memory segment, you have to attach yourself to it using shmat(). void *shmat(int shmid ,void *shmaddr ,int shmflg);
shmid is a shared memory id. shmaddr specifies a specific address to use but we should set
it to zero and OS will automatically choose the address.

shmdt(): When you’re done with the shared memory segment, your program should 
detach itself from it using shmdt(). int shmdt(void *shmaddr);

shmctl(): when you detach from shared memory,it is not destroyed. So, to destroy 
shmctl() is used.  shmctl(int shmid,IPC_RMID,NULL);

Interprocess Communication (IPC) is a mechanism that allows processes to communicate with each other and synchronize their actions. The communication between these processes can be seen as a method of co-operation between them. Processes can communicate with each other using these two ways:



• Shared Memory Communication between processes using shared memory requires processes to share some variable and it completely depends on how the programmer will implement it.
  The Figure 1 below shows a basic structure of communication between processes via shared memory method and via message passing.
  
  Example of shared memory: Producer consumer problem



• Message passing: In message passing method processes communicate with each other without using any kind of shared memory. If two processes p1 and p2 want to communicate with each other, they proceed as follow:
  
  
  • Establish a communication link (if a link already exists, no need to establish it again.)
  • Start exchanging messages using basic primitives.
    We need at least two primitives:
    – send(message, destinaion) or send(message)
    – receive(message, host) or receive(message)




The message size can be of fixed size or of variable size. if it is of fixed size, it is easy for OS designer but complicated for the programmer and if it is of variable size then it is easy for the programmer but complicated for the OS designer. A standard message can have two parts: header and body. The header part is used for storing Message type, destination id, source id, message length and control information. The control information contains information like what to do if runs out of buffer space, sequence number, the priority. Generally, the message is sent using the FIFO style.
A message queue is a linked list of messages stored within the kernel and identified by a message queue identifier. A new queue is created or an existing queue opened by msgget().
New messages are added to the end of a queue by msgsnd(). Every message has a positive long integer type field, a non-negative length, and the actual data bytes (corresponding to the length), all of which are specified to msgsnd() when the message is added to a queue. Messages are fetched from a queue by msgrcv(). We don't have to fetch the messages in a first-in, first-out order. Instead, we can fetch messages based on their type of field.

All processes can exchange information through access to a common system message queue. The sending process places a message (via some (OS) message-passing module) onto a queue that can be read by another process. Each message is given an identification or type so that processes can select the appropriate message. The process must share a common key in order to gain access to the queue in the first place.



System calls used for message queues:


ftok(): is use to generate a unique key.

msgget(): either returns the message queue identifier for a newly created message 
queue or returns the identifiers for a queue that exists with the same key value.

msgsnd(): Data is placed on to a message queue by calling msgsnd().

msgrcv(): messages are retrieved from a queue.

msgctl(): It performs various operations on a queue. Generally it is use to 
destroy message queue.

Let's understand the working of Lock mechanism using the following example:

Previously we saw that this problem provided inconsistent results. Now, let's add the lock mechanism into this piece of code:

Let's analyze the mechanism. Although we have applied the locking mechanism, still the code doesn't guarantee mutual exclusion that is a mandatory requirement. Suppose in the deposit part, the process gets preempted just after the while statement and the control flows to the Withdraw part. After the execution, when the control flows back to the Deposit part, it enters the critical section. Therefore, the principle of mutual exclusion is violated, as both the processes might enter the critical section and cause a race condition.
To avoid this we use a hardware-based implementation called Test and Set or the TSL lock mechanism.
Deposit and Withdraw mechanism using TSL lock:

This TSL lock work both ways, it waits while the lock is true and also the lock is updated as true if it is false. This function doing both the things has to be atomic. So this is an atomic operation to acquire the lock and once it is acquired nobody else could acquire the lock. This solves the basic problem of Process Synchronization.

Problem with Locking Mechanism: In the previous lectures, we have seen how the locking mechanism facilitates process execution by applying locks when a process enters the critical section and releasing it when the job is done. While doing this other processes had to wait and they went into a waiting loop until the process inside completes its execution. This is a major problem and can be avoided using Semaphores.

Semaphore: Semaphore is simply a variable. This variable is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment. The two most common kinds of semaphores are counting semaphores and binary semaphores. Counting semaphore can take non-negative integer values and Binary semaphore can take the value 0 & 1 only.

1. Counting Semaphore: Let's see how this works using a restroom analogy. Suppose there is a restroom(critical section) which is being used by a person(process). When another process comes, he had to wait until the previous process comes out and releases the lock. All the upcoming processes had to go into a waiting loop. This problem can be avoided using a semaphore. Consider a semaphore is like a guard who maintains a record and as long as a process is inside the restroom, it tells all other processes to sleep or do any other task and not to go into a waiting loop. When the process inside completes its execution, the guard informs the process in the queue and it can enter the restroom.
   To perform this complex process, the guard or the semaphore maintains a record. It maintains two functions namely, wait and signal.
   
   wait(): The wait keeps a record of the count. The count is initially assigned a value equal to the number of available resources. Every time a process is allocated to a resource, the value of count is decreased by one. Once the value of count is negative, it indicates that all the resource is underuse and the address of the PCB of the upcoming processes are stored in a queue. This way, the processes are not kept waiting. The negative value now indicates the number of processes outside who need to use the resource.
   
   signal(): The signal function increments the value of count by one every time a process finish using a resource which can be made available to some other process. The guard wakes or signals a process in the queue when the count is decremented, that a resource is free to use and releases a process in the FCFS basis.
   
   Let's write a pseudo code for the above process. For start we assume there are 3 available resources. So count will be initialized as 3. We have a semaphore containing a count and queue, to keep track of the processes.
   
   PseudoCode:
   }

   1

   2

   3

   4

   5

   6

   7

   8

   9

   10

   11

   12

   13

   14

   15

   16

   17

   18

   19

   20

   21

   22

   23

   24

   25

   26

   27

   28

   29

   30

   // A semaphore structure having count and queue

   struct Sem{

   int count; Queue q;

   }

   // Creating variable s of semaphore where count = 3 and q is empty

   Sem s(3, empty);

   // Used while entering into the washroom or the critical section

   void wait(){

   // process before entering CS

   s.count--;

   // No resource is available

   if(s.count < 0){

   // No resource is available

   1. Add the caller process P to q;

   2. sleep(P);

   }

   }

   // Used while exiting from the washroom or the critical section

   void signal(){

   // process after exiting CS

   s.count++;

   // Checking for process in queue

   if(s.count <= 0)

   {

   1. Remove a process P from q

   2. Wakeup(P);

   }

   }

   Run
   
   
   Now let's look at two operations that can be used to access and change the value of the semaphore variable and how this was originally implemented by Dijkstra:
   
   
   
   Some point regarding P and V operation
   1. P operation is also called wait, sleep or down operation and V operation is also called signal, wake-up or up operation.
   2. Both operations are atomic and semaphore(s) is always initialized to one.
   3. A critical section is surrounded by both operations to implement process synchronization. See below image critical section of Process P is in between P and V operation.
   
   
   This PV operation comes with few problems like busy waiting, as the while loop keeps running when the process does not get a resource or critical section. This way the CPU cycle gets wasted.
   Another problem is that of bounded waiting when a process because of preemption might not get a resource for a very long time. These problems have been solved in the previous discussion where we have used count, queue and sleep and wake up concept to make efficient use of CPU ans see that no CPU cycle is wasted.



2. Binary Semaphore: In a binary semaphore, the counter logically goes between 0 and 1. You can think of it as being similar to a lock with two values: open/closed. In binary semaphore, only two processes can enter into the critical section at any time and mutual exclusion is also guaranteed. Let's look a the pseudo-code below to understand the logic behind the implementation of binary semaphore. This Binary Semaphore can be used as mutex too with the additional functionalities like sleep and wake concept etc. Let's look at the pseudo-code:
   
   Queue q;

   1

   2

   3

   4

   5

   6

   7

   8

   9

   10

   11

   12

   13

   14

   15

   16

   17

   18

   19

   20

   21

   22

   23

   24

   25

   26

   27

   28

   29

   30

   31

   // Binary Semaphore containing

   // a boolean value and queue q

   // to keep track of processes

   // entering critical section

   struct BinSem

   {

   bool val;

   Queue q;

   };

   // Global initialization

   BinSem s(true, empty);

   // wait() is called before critical section

   // during entry

   void wait()

   {

   // Checking if critical section is

   // available or not

   if (s.val == 1)

   // acquiring the critical section

   s.val = 0;

   // if not available

   else

   {

   1. Put this process P in q;

   2. sleep(P);

   }

   Run

// Binary Semaphore containing
// a boolean value and queue q
// to keep track of processes
// entering critical section
struct BinSem
{
    bool val;
    Queue q;
};

// Global initialization
BinSem s(true, empty);

// wait() is called before critical section
// during entry
void wait()
{
    // Checking if critical section is
    // available or not
    if (s.val == 1)
        // acquiring the critical section
        s.val = 0;
    
    // if not available
    else
    {
        1. Put this process P in q;
        2. sleep(P);
    }
}

// signal() is called after critical section
// during exit
void signal
{
    if (q is empty)
        s.val = 1;
    else
    {
        1. Pick a process P from q;
        2. Wakeup(P);
    }
}

Implementation of Mutual Exclusion: Now, let us see how it implements mutual exclusion. Let there be two processes P1 and P2 and a semaphore s is initialized as 1. Now if suppose P1 enters in its critical section then the value of semaphore s becomes 0. Now if P2 wants to enter its critical section then it will wait until s > 0, this can only happen when P1 finishes its critical section and calls V operation on semaphore s. This way mutual exclusion is achieved. Look at the below image for details.



The description above is for binary semaphore which can take only two values 0 and 1. There is one other type of semaphore called counting semaphore which can take values greater than one.

Now suppose there is a resource whose number of instances is 4. Now we initialize S = 4 and rest is the same as for binary semaphore. Whenever the process wants that resource it calls P or wait() function and when it is done it calls V or signal function. If the value of S becomes zero then a process has to wait until S becomes positive. For example, Suppose there are 4 processes P1, P2, P3, P4 and they all call wait operation on S(initialized with 4). If another process P5 wants the resource then it should wait until one of the four processes calls signal function and the value of semaphore becomes positive.

Problem in this implementation of semaphore
Whenever any process waits then it continuously checks for semaphore value (look at this line while (s==0); in P operation) and waste CPU cycle. To avoid this another implementation is provided below.

• In this implementation whenever process waits it is added to a waiting queue of processes associated with that semaphore. This is done through the system call block() on that process. When a process is completed it calls signal function and one process in the queue is resumed. It uses wakeup() system call.
  
  
  
  • A mutex is a binary variable whose purpose is to provide a locking mechanism. It is used to provide mutual exclusion to a section of code, which means only one process can work on a particular code section at a time.
    
    
  • There is misconception that binary semaphore is same as mutex variable but both are different in the sense that binary semaphore apart from providing locking mechanism also provides two atomic operation signal and wait, means after releasing resource semaphore will provide signaling mechanism for the processes who are waiting for the resource.

What are the differences between Mutex vs Semaphore? When to use mutex and when to use semaphore?

As per operating system terminology, mutex and semaphore are kernel resources that provide synchronization services (also called as synchronization primitives). Why do we need such synchronization primitives? Won't be only one sufficient? To answer these questions, we need to understand a few keywords. Please read the posts on the critical section. We will illustrate with examples to understand these concepts well, rather than following the usual OS textual description.

The producer-consumer problem:


Consider the standard producer-consumer problem. Assume, we have a buffer of 4096-byte length. A producer thread collects the data and writes it to the buffer. A consumer thread processes the collected data from the buffer. The objective is, both the threads should not run at the same time.

• Using Mutex:
  A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by the producer, the consumer needs to wait, and vice versa.
  
  At any point of time, only one thread can work with the entire buffer. The concept can be generalized using a semaphore.
  
  
• Using Semaphore:
  A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.

Misconception:

• There is an ambiguity between binary semaphore and mutex. We might have come across that a mutex is a binary semaphore. But they are not! The purpose of mutex and semaphore is different. Maybe, due to the similarity in their implementation a mutex would be referred to as a binary semaphore.
  
  
• Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there is ownership associated with a mutex, and only the owner can release the lock (mutex).
  
  
• Semaphore is signaling mechanism ("I am done, you can carry on" kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend calls you, an interrupt is triggered upon which an interrupt service routine (ISR) signals the call processing task to wakeup.

Note: The content is generalized explanation. Practical details vary with implementation.
 
General Questions:

1. Can a thread acquire more than one lock (Mutex)?
   Yes, it is possible that a thread is in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.
   
   
2. Can a mutex be locked more than once?
   A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.
   
   
3. What happens if a non-recursive mutex is locked more than once.
   Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in a deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of the mutex and return if it is already locked by the same thread to prevent deadlocks.
   
   
4. Are binary semaphore and mutex same?
   No. We suggest to treat them separately, as it is explained by signaling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with a mutex. We will cover these in a later article.
   
   A programmer can prefer mutex rather than creating a semaphore with count 1.
   
   
5. What are a mutex and critical section?
   Some operating systems use the same word critical section in the API. Usually, a mutex is a costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.
   
   
6. What are events?
   The semantics of mutex, semaphore, event, critical section, etc... are the same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for the exact details.
   
   
7. Can we acquire mutex/semaphore in an Interrupt Service Routine?
   An ISR will run asynchronously in the context of the current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR is meant to be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.
   
   
8. What we mean by "thread blocking on mutex/semaphore" when they are not available?
   Every synchronization primitive has a waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of the processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list gets the resource (more precisely, it depends on the scheduling policies).
   
   
9. Is it necessary that a thread must block always when the resource is not available?
   Not necessary. If the design is sure 'what has to be done when the resource is not available', the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.
   
   For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function returns immediately whereas the API pthread_mutex_lock() blocks the thread till resource is available.

The monitor is one of the ways to achieve Process synchronization. The monitor is supported by programming languages to achieve mutual exclusion between processes. For example Java Synchronized methods. Java provides wait() and notify() constructs.

1. It is the collection of condition variables and procedures combined together in a special kind of module or a package.


2. The processes running outside the monitor can't access the internal variable of the monitor but can call procedures of the monitor.


3. Only one process at a time can execute code inside monitors.

Syntax of Monitor

The idea of implementing monitors is that instead of going into the complexities of acquiring, lease, wait for the signal, we use a class and put various functions inside it and synchronize the whole mechanism.

Example:
Condition Variables
Two different operations are performed on the condition variables of the monitor.

Wait.

signal.

let say we have 2 condition variables
condition x, y; //Declaring variable
 

Wait operation x.wait() : Process performing wait operation on any condition variable are suspended. The suspended processes are placed in block queue of that condition variable.

Note: Each condition variable has its unique block queue.

 

Signal operation x.signal(): When a process performs signal operation on condition variable, one of the blocked processes is given chance.

If (x block queue empty)

  // Ignore signal

else

  // Resume a process from block queue.

A process in operating systems uses different resources and uses resources in the following way.
1) Requests a resource
2) Use the resource
2) Releases the resource



Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. A similar situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for the resource

This can also occur for more than two processes as shown in the below diagram:




Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions)

1. Mutual Exclusion: One or more than one resource are non-sharable (Only one process can use at a time)


2. Hold and Wait:A process is holding at least one resource and waiting for resources.


3. No Preemption:A resource cannot be taken from a process unless the process releases the resource.


4. Circular Wait: A set of processes are waiting for each other in circular form.

Resource allocation graph: As Banker's algorithm using some kind of table like allocation, request, available all that thing to understand what is the state of the system. Similarly, if you want to understand the state of the system instead of using those tables, actually tables are very easy to represent and understand it, but then still you could even represent the same information in the graph. That graph is called Resource Allocation Graph (RAG).

So, the resource allocation graph is explained to us what is the state of the system in terms of processes and resources. Like how many resources are available, how many are allocated and what is the request of each process. Everything can be represented in terms of the diagram. One of the advantages of having a diagram is, sometimes it is possible to see a deadlock directly by using RAG, but then you might not be able to know that by looking at the table. But the tables are better if the system contains lots of process and resource and Graph is better if the system contains less number of process and resource.
We know that any graph contains vertices and edges. So RAG also contains vertices and edges. In RAG vertices are two type -

1. Process vertex - Every process will be represented as a process vertex.Generally, the process will be represented with a circle.


2. Resource vertex - Every resource will be represented as a resource vertex. It is also two type -
   
   • Single instance type resource - It represents as a box, inside the box, there will be one dot.So the number of dots indicate how many instances are present of each resource type.
   • Multi-resource instance type resource - It also represents as a box, inside the box, there will be many dots present.

Now coming to the edges of RAG. There are two types of edges in RAG -

1. Assign Edge - If you already assign a resource to a process then it is called Assign edge.
2. Request Edge - It means in future the process might want some resource to complete the execution, that is called request edge.



So, if a process is using a resource, an arrow is drawn from the resource node to the process node. If a process is requesting a resource, an arrow is drawn from the process node to the resource node.
Example 1 (Single instances RAG) -


If there is a cycle in the Resource Allocation Graph and each resource in the cycle provides only one instance, then the processes will be in a deadlock. For example, if process P1 holds resource R1, process P2 holds resource R2 and process P1 is waiting for R2 and process P2 is waiting for R1, then process P1 and process P2 will be in a deadlock.



Here's another example, that shows Processes P1 and P2 acquiring resources R1 and R2 while process P3 is waiting to acquire both resources. In this example, there is no deadlock because there is no circular dependency.
So cycle in single-instance resource type is the sufficient condition for deadlock.
Example 2 (Multi-instances RAG) -


From the above example, it is not possible to say the RAG is in a safe state or in an unsafe state. So to see the state of this RAG, let's construct the allocation matrix and request matrix.

• The total number of processes are three; P1, P2 & P3 and the total number of resources are two; R1 & R2.

Allocation matrix -
• For constructing the allocation matrix, just go to the resources and see to which process it is allocated.
• R1 is allocated to P1, therefore write 1 in allocation matrix and similarly, R2 is allocated to P2 as well as P3 and for the remaining element just write 0.

Request matrix -
• In order to find out the request matrix, you have to go to the process and see the outgoing edges.
• P1 is requesting resource R2, so write 1 in the matrix and similarly, P2 requesting R1 and for the remaining element write 0.

So now available resource is = (0, 0).

Checking deadlock (safe or not) -




So, there is no deadlock in this RAG. Even though there is a cycle, still there is no deadlock. Therefore in multi-instance resource cycle is not sufficient condition for deadlock.




The above example is the same as the previous example except that, the process P3 requesting for resource R1.
So the table becomes as shown in below.




So,the Available resource is = (0, 0), but requirement are (0, 1), (1, 0) and (1, 0).So you can't fulfill any one requirement.Therefore, it is in deadlock.

Therefore, every cycle in a multi-instance resource type graph is not a deadlock, if there has to be a deadlock, there has to be a cycle. So, in case of RAG with a multi-instance resource type, the cycle is a necessary condition for deadlock, but not sufficient.

Methods for handling deadlock There are three ways to handle deadlock

1. Deadlock Prevention: The OS accepts all the sent requests. The idea is to not to send a request that might lead to a deadlock condition.


2. Deadlock Avoidance: The OS very carefully accepts requests and checks whether if any request can cause deadlock and if the process leads to deadlock, the process is avoided.



3. Deadlock Detection and Recovery: Let deadlock occur, then do preemption to handle it once occurred.


4. Ignore the problem altogether: If the deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

Deadlock Characteristics As discussed in the previous post, deadlock has following characteristics.

1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait

 

Deadlock Prevention
We can prevent Deadlock by eliminating any of the above four conditions.

• Eliminate Mutual Exclusion: It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tap drive and printer, are inherently non-shareable. It can be avoided to some extent using Spooling.


 


• Eliminate Hold and wait:
  1. Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the start of its execution printer will remain blocked till it has completed its execution.
     
     
  2. The process will make a new request for resources after releasing the current set of resources. This solution may lead to starvation.
  




• Eliminate No Preemption: Preempt resources from the process when resources required by other high priority processes.


 


• Eliminate Circular Wait: Each resource will be assigned with a numerical number. A process can request the resources only in increasing order of numbering.
  For Example, if the P1 process is allocated R1, P2 has R2 and P3 has R3, then P3 cannot request R1 which is less than R3.
  
  
  

 

 

Deadlock Avoidance
Deadlock avoidance can be done with Banker's Algorithm.

If a system does not employ either a deadlock prevention or deadlock avoidance algorithm then a deadlock situation may occur. In this case-

• Apply an algorithm to examine state of system to determine whether deadlock has has occurred or not.
• Apply an algorithm to recover from the deadlock. For more refer- Deadlock Recovery

Deadlock Detection Algorithm/Bankers Algorithm: It is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
The algorithm employs several time varying data structures:

• Available- A vector of length m indicates the number of available resources of each type.
• Allocation- An n*m matrix defines the number of resources of each type currently allocated to a process. Column represents resource and resource represent process.
• Request- An n*m matrix indicates the current request of each process. If request[i][j] equals k then process P_i is requesting k more instances of resource type R_j.

We treat rows in the matrices Allocation and Request as vectors, we refer them as Allocation_i and Request_i.

Steps of Algorithm:

1. Let Work and Finish be vectors of length m and n respectively. Initialize Work= Available. For i=0, 1, ...., n-1, if Allocation_i = 0, then Finish[i] = true; otherwise, Finish[i]= false.
2. Find an index i such that both
   a) Finish[i] == false b) Request_i <= Work If no such i exists go to step 4.
3. Work= Work+ Allocation_i Finish[i]= true Go to Step 2.
4. If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process P_i is deadlocked.

Example 1:

    
In this, Work = [0, 0, 0] &

     Finish = [false, false, false, false, false]

   
i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].

   
Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &

    Finish = [true, false, false, false, false]. 

   
i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].

   
Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &

       Finish = [true, false, true, false, false].

   
i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3]. 

   
Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &

     Finish = [true, true, true, false, false]. 

   
i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3].

   
Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &

     Finish = [true, true, true, true, false]. 

   
i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].  

   
Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &

     Finish = [true, true, true, true, true]. 

   
Since Finish is a vector of all true it means there is no deadlock in this example.

Example 2:
Considering a system with five processes P₀ through P₄ and three resources of type A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t₀ following snapshot of the system has been taken:

Question1. What will be the content of the Need matrix?
Need [i, j] = Max [i, j] – Allocation [i, j]

So, the content of Need Matrix is:


Question2.  Is the system in a safe state? If Yes, then what is the safe sequence?
Applying the Safety algorithm on the given system,


Question3. What will happen if process P₁ requests one additional instance of resource type A and two instances of resource type C?

We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the above data structures.


Hence the new system state is safe, so we can immediately grant the request for process  P_{1 .}

There are three basic approaches to recover from deadlock:

1. Allow users to take manual intervention and inform the system operator.
   
2. Terminate one or more than one process which is involved in the deadlock.
   
3. Preempt resources.

How to terminate the process:

• There are two basic approaches to terminate processes and recover the resources allocated to those processes.
  
  • Terminate all processes involved in deadlock. Deadlock will be recovered but at the expense of more processes termination.
    
  • Terminate processes one by one until the deadlock is broken, this is a conservative approach and requires deadlock detection after each step.
• In another approach there are many factors that will decide which processes to terminate next:
  
  • Process priorities.
    
  • Running time of processes and remaining time to finish.
    
  • What type of resources are held by process and how many processes are held by the process.
    
  • How many requests for resources are made by the process.
    
  • How many processes need to be terminated.
    
  • Is the process interactive or batch?
    
  • Is there any non-restorable changes has been made by any process?

Resources preemption: There are three main issues to be addressed while relieving deadlock

• Selecting a victim It is a decision making the call to decide which resource must be released by which process. Decision criteria are discussed in the above section.
  
• Rollback Once the resources are taken back from a process, it is hard to decide the safe state in rollback or what is safe rollback. So, the safest rollback is the starting or beginning of the process.
  
• Statrvation: Once the preemption of resources started there is higher chance of starvation of process. Starvation can be avoided or can be decreased by the priority system.
  

Example:
Let's take this sample code to understand the various steps.
Step 1: The above code is the source code which is passed to the compiler.

Step 2: The compiler converts this source code to machine-executable object code.

Step 3: Then Linker is used to linking the functions mentioned inside the main function. Here "printf()" is a library function, whose code is attached to the main function using the linker. The linking can be done statically or dynamically.

• Static Linking: In this, the code of the "printf" function is copied into the object file and then one executable file is generated and the execution is done line by line.


• Dynamic Linking: This refers to the linking that is done during load or run-time and not when the file is created. When one program is dependent on some other program rather than loading all the dependent programs, CPU links the dependent programs to the main executing program when it's required.
  

Step 4: After the creation of the executable file the loader copies the executable code into the main memory.

Step 5: Finally the code is run in the main memory and while running dynamic linking can be made with other system libraries.

Address binding refers to the mapping of relocatable or relative address to physical addresses. The binary of code contains relative or relocatable addresses which are used to commute between various instructions. There can be various binary instructions ranging from goto, load, add etc. To execute this sort of binary files, they are needed to be loaded into the main memory. This main memory has physical addresses, and any processes stored in the main memory acquires a slot. The physical addresses of the main memory influence the binary addresses accordingly by readjusting them accordingly. For eg., when the binary file is loaded into the slot after 50k, they are readjusted to 50k, 50k+1, 50k+2, 50k+3 etc.

These bindings can happen at various stages of execution:

1. Compile Time: Its work is to generate a logical address(also known as virtual address). If you know that during compile time where the process will reside in memory then the absolute address is generated.
   
   • Instruction are translated into an absolute address.
   
   
   • It works with the logical address.
   
   
   • It is static.
   
   
   • Code is compiled here.



2. Load time: It will generate a physical address. If at the compile-time it is not known where the process will reside then relocatable address will be generated. In this, if address changes then we need to reload the user code.
   
   • Absolute address is converted to relocatable address
   
   
   • It works with a physical address
   
   
   • It is static
   
   
   • Instructions are loaded in memory
   
   Problem with Load Time Binding is that once it is loaded into the main memory, it cannot be relocated. Let's look at this example:
   
   Suppose there is this process P1 which is loaded at 50k of the main memory. If it is waiting for some I/O, then the process is swapped out to make the memory available to some other processes. Now, when P1 completes its I/O work and it is swapped back into the main memory, the process is stored at some different address, suppose 150k. This cannot be implemented in Load Time binding.
   
   


3. Run Time: It is the most preferred binding technique in modern OS. The addresses generated by the CPU during the run time are logical addresses and not the physical addresses. This logical address is then converted into physical addresses using a memory-management unit(MMU). This is used in the process can be moved from one memory to another during execution(dynamic linking-Linking that is done during load or run time). Hardware support is required during run time-binding.
   
   
   • The dynamic absolute address is generated.
   
   
   • It works in between and helps in execution.
   
   
   • It is dynamic.
   
   
   • From memory, instructions are executed by CPU.

Runtime Binding happens through hardware. The memory management unit in CPU has two registers namely, Limit Register and the Relocation Register. When a process is loaded into the memory, during context switching, the OS automatically loads these registers into the memory. The registers are loaded according to the slots in the memory.



The process begins with the CPU generating the logical addresses. Then the process is sent to the memory management unit where the limit register first checks whether the generated logical address is within or beyond the memory allocation. If the address is beyond the limit, a trap is sent to the OS else the control flows to the Relocation register which relocates or adjusts the address and converts the logical address to physical address.

Why is the whole process implemented in hardware?
If a software implements this runtime binding, then during the context switching, when the logical address is generated, an OS system call will happen, which will convert the logical address to physical address. This will require Mode switching from process to OS context which will be done for every instruction, generated by the CPU. This will be a very slow process and hence the hardware is implemented to do the binding.

The memory management evolved in two phases:
Single Tasking Systems: This sort of system has a part loaded with OS. When one process arrives it is assigned to a slot and only after its completion can a second process be allowed a slot in the memory. Suppose in the diagram only after the execution of P1 completes can a process P2 be loaded into the memory.

The problem with this system was that the context switching could not take place in a single-tasking system when multiple processes are sent into the memory. This results in a low degree of multiprogramming leading to the less efficient use of CPU.

Multitasking Systems: In this multiple processes can be taken by the memory at a single time and each process are run one by one using efficient memory management techniques, leading to the higher degree of multiprogramming. In the below diagram we can see that P1, P2 and P3 are stored inside the memory at the same time and can be run simultaneously.


There can be various types of memory management allocation technique in Multitasking.



Static or Fixed Partitioning Technique: This is the oldest and simplest technique used to put more than one processes in the main memory. In this partitioning, a number of partitions (non-overlapping) in RAM is fixed but the size of each partition may or may not be same. As it is contiguous allocation, hence no spanning is allowed. Here partition is made before execution or during system configure. This can be of two types:

1. Equal Size Memory Allocation: In this technique, fixed memory size is allocated to each process. Let's look at the below example:
   
   In this case, each process P1, P2 and P3 are allocated 10MB each irrelevant of how much memory each process requires. Suppose P1 had a demand of 8MB, P2 7MB and P3 6Mb. After each allocation, we can see that 2MB, 3MB, and 4Mb of memory is wasted from each slot. Although it adds up to 9 Mb, when a process P4 demands 5Mb of memory, it cannot be allocated, since they are available in different chunks. This phenomenon is referred to as external fragmentation. Let's understand fragmentation:
   Fragmentation occurs in a dynamic memory allocation system when many of the free blocks are too small to satisfy any request.
   
   
   • External Fragmentation: External Fragmentation happens when a dynamic memory allocation algorithm allocates some memory and a small piece is left over that cannot be effectively used. If too much external fragmentation occurs, the amount of usable memory is drastically reduced. Total memory space exists to satisfy a request, but it is not contiguous.
   
   
   • Internal Fragmentation: Internal fragmentation is the space wasted inside of allocated memory blocks because of restriction on the allowed sizes of allocated blocks. Allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used.
   
   In the case of equal size memory allocation, internal fragmentation leads to external fragmentation. This results in high memory loss since we can observe that 9 MB of memory goes wasted.
   


2. Unequal Size Memory allocation: This technique is used to reduce memory loss in comparison to the equal size memory allocation. Let's look at the below example.
   
   Suppose we want to allocate a process of 3 MB to the memory. Instead of allocating it to a fixed size of memory, a minimum MB slot is found and P1 is allocated to it. In our case, the 4MB slot is allocated to P1 consuming 3MB memory. If another process P2 arrives with a memory requirement of less than 2 Mb, then the first slot is allocated to it. Similarly, another process of 7Mb can take the 8Mb slot. So, we can see that although here also there is memory loss due to internal fragmentation and ultimately leading to external fragmentation, it is less in comparison to the Equal size memory allocation. Here there is a memory loss of total 3 MBs.

Advantages of Fixed Partitioning:

1. Easy to implement: Algorithms needed to implement Fixed Partitioning are easy to implement. It simply requires putting a process into certain partition without focussing on the emergence of Internal and External Fragmentation.
   


2. Little OS overhead: Processing of Fixed Partitioning require lesser excess and indirect computational power.
   

Disadvantages of Fixed Partitioning -

1. Internal Fragmentation: Main memory use is inefficient. Any program, no matter how small, occupies an entire partition. This can cause internal fragmentation.
   


2. External Fragmentation: The total unused space (as stated above) of various partitions cannot be used to load the processes even though there is space available but not in the contiguous form (as spanning is not allowed).
   


3. Limit process size: Process of size greater than size of partition in Main Memory cannot be accommodated. Partition size cannot be varied according to the size of incoming process's size. Hence, process size of 32MB in above stated example is invalid.
   


4. Limitation on Degree of Multiprogramming: Partition in Main Memory are made before execution or during system configure. Main Memory is divided into fixed number of partition. Suppose if there are $n1$ partitions in RAM and $n2$ are the number of processes, then $n2\le n1$ condition must be fulfilled. Number of processes greater than number of partitions in RAM is invalid in Fixed Partitioning.
   

Dynamic or Variable Partitioning Technique:
It is a part of Contiguous allocation technique. It is used to alleviate the problem faced by Fixed Partitioning. In contrast with fixed partitioning, partitions are not made before the execution or during system configure. Various features associated with variable Partitioning-

1. Initially RAM is empty and partitions are made during the run-time according to process's need instead of partitioning during system configure.
   


2. The size of partition will be equal to incoming process.
   


3. The partition size varies according to the need of the process so that the internal fragmentation can be avoided to ensure efficient utilisation of RAM.
   


4. Number of partitions in RAM is not fixed and depends on the number of incoming process and Main Memory's size.
   

There are some advantages and disadvantages of variable partitioning over fixed partitioning as given below.

Advantages of Variable Partitioning -

1. No Internal Fragmentation: In variable Partitioning, space in main memory is allocated strictly according to the need of process, hence there is no case of internal fragmentation. There will be no unused space left in the partition.
   


2. No restriction on Degree of Multiprogramming: More number of processes can be accommodated due to absence of internal fragmentation. A process can be loaded until the memory is not empty.
   


3. No Limitation on the size of the process: In Fixed partitioning, the process with the size greater than the size of the largest partition could not be loaded and process can not be divided as it is invalid in contiguous allocation technique. Here, In variable partitioning, the process size can't be restricted since the partition size is decided according to the process size.
   

Disadvantages of Variable Partitioning -

1. Difficult Implementation: Implementing variable Partitioning is difficult as compared to Fixed Partitioning as it involves allocation of memory during run-time rather than during system configure.
   


2. External Fragmentation: There will be external fragmentation inspite of absence of internal fragmentation.
   
   For example, suppose in above example- process P1(2MB) and process P3(1MB) completed their execution. Hence two spaces are left i.e. 2MB and 1MB. Let's suppose process P5 of size 3MB comes. The empty space in memory cannot be allocated as no spanning is allowed in contiguous allocation. The rule says that the process must be contiguously present in main memory to get executed. Hence it results in External Fragmentation. These spaces are called holes.
   
   
   
   Now P5 of size 3 MB cannot be accommodated in spite of required available space because in contiguous no spanning is allowed.
   

The major disadvantage of dynamic partitioning is that when a process completes its execution, it leaves the memory leaving a hole behind. Thus when multiple processes leave, similar holes are created and thus even if there is no internal fragmentation, external fragmentation is observed.

There are two methods to avoid such holes:

1. Bitmap: These are used to keep a track of the unit of memories that are occupied as 1 and the unallocated memories are assigned 0. So when a new process comes, it looks for the 0's to get a track of unallocated spaces and thus the problem is solved. This way memory management is made simpler and easier.
   
   It also has a major problem. Bitmap requires a lot of space. Since for every unit of memory, a bit is needed in the bitmap to store the value. Eg., Suppose we have a memory unit of size 32 bit. So for every 32 unit, 1 bit of memory is needed to store the bit in the bitmap. Therefore for 32 bits, one bit is wasted. So 1 by 33 of the memory is wasted in the process.
   If a larger size of the unit is taken, then this might lead to internal fragmentation. So both the processes are not feasible.
   


2. Linked List: In this the processes and the holes are connected using a doubly-linked list. So if a process ends in between, then the holes get connected to form a bigger hole. In the below diagram if P2 completes its execution, then both the H combines and a greater hole is generated, which can accommodate any incoming process of relevant size. But, there is a catch of how to allocate memory as in what process should get which holes. We have various strategies to do so. Let's discuss:
   
   In Partition Allocation, when there is more than one partition freely available to accommodate a process's request, a partition must be selected. To choose a particular partition, a partition allocation method is needed. A partition allocation method is considered better if it avoids internal fragmentation.
   
   Below are the various partition allocation schemes :
   
   1. First Fit: In the first fit, the partition is allocated which is first sufficient block from the top of Main Memory. Let's look at the example below:
      
      Suppose in this setup a process P4 of size 5 MB makes a request. In First Fit, the linked list is traversed from the top of the memory and wherever, a size of 5 MB or more is available, the process gets allocated. In this case, the P4 gets allocated in the 10 MB hole leaving another hole of 5 MB. Now if another request of 3 MB is requested then it gets stored in this 5 MB hole. Again if a 10 MB request arrives, then the linked list is traversed from the top and since only the 12 MB hole can accommodate the request, it gets allocated here.
      
      
   
   
   2. Best Fit: Allocate the process to the partition which is the first smallest sufficient partition among the free available partition. Let's look at the example below:
      
      Suppose in this setup a process P4 of size 3 MB makes a request. In Best Fit, the linked list is traversed from the top of the memory and instead of assigning the process to wherever the sufficient memory is available, it keeps a track of the minimum block which can accommodate the process. In this case the P4 with 3 MB is assigned to the 4 MB block even if 10 MB block is first encountered. It has a few disadvantages:
      
      • Every time a process makes a request, the whole linked list is needed to be traversed, thus this approach has greater time complexity.
      • Various small memory holes are created which remains unused as this could not be assigned to any processes.
   3. Next Fit: Next fit is similar to the first fit but it will search for the first sufficient partition from the last allocation point. Let's look at the example below:
      
      Suppose in this setup a process P4 of size 8 MB and a process P5 of size 3 MB makes a request. At first, the linked list is traversed from the top of the memory and wherever, a size of 8 MB or more is available, the process gets allocated. In this case, the P4 gets allocated in the 10 MB hole leaving another hole of 2 MB. When the next request P5 of 3 MB arrives then, instead of traversing the whole list from the top, it is traversed from the last stop i.e., from P4 and process P5 gets allocated into the 4 MB block.
      
   
   
   4. Worst Fit: Allocate the process to the partition which is the largest sufficient among the freely available partitions available in the main memory.
   
   
   
   After doing some analysis, it has been found out that the First fit is the best approach since the best-fit algorithm needs to traverse the whole list every time a request is made.